package 实验;
import 线性表.List;
import 线性表.顺序表.SeqList;

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        //测试接口方法
        funTest();
        //测试merge方法
        mergeTest(10000);
    }

    private static List merge(List list1, List list2) {
        List lists = new SeqList(list1.getSize()+list2.getSize());        //定义一个新数组
        for (int i = 0; i < list1.getSize(); i++) {     //将list1放进去
            lists.insertAt(i + 1,list1.get(i));
        }
        int a = 0;
        for (int i = lists.getSize() + 1; i <= list1.getSize() + list1.getSize(); i++) {//将list2放进去
            lists.insertAt(i ,list2.get(a));
            a++;
        }
        List helpLists = new SeqList(lists.getSize()); //复制一份
        //因为是一个对象，不能使用 helpLists = lists 只能对它进行操作
        for (int i = 0; i <lists.getSize() ; i++) {
            helpLists.insertAt(i + 1,lists.get(i));
        }
        int left = 0;                //左指针
        int right = list1.getSize(); //右指针
        for (int i = 0; i < lists.getSize() - 1; i++) {
            if ((int) helpLists.get(right) <= (int)helpLists.get(left)) {
                if (right == lists.getSize() - 1 ) {  //右边已经扫完,将左边剩余的补上
                    lists.replace(i,helpLists.get(right));
                    for (int j = left + 1; j < list1.getSize(); j++) {
                        i++;
                        lists.replace(i,helpLists.get(left));
                        left++;
                    }
                }else {
                    lists.replace(i,helpLists.get(right));                          //覆盖原来数组
                    right++;
                }
            }
            else {
                if (left >= list1.getSize() ) {
                    break;              //左边已扫完不做任何操作
                }else {
                    lists.replace(i,helpLists.get(left));
                    left++;
                }
            }
        }
        return lists;
    }

    private static List merge1(List list1, List list2) {
        for (int j = 0; j < list2.getSize()/2; ++j) {
            int nums = (int) list2.get(j);
            int i;
            for ( i = 0; i < list1.getSize()/2; i++) {
                if (nums < Integer.parseInt((list1.get(i)).toString())) {
                    break;
                }
            }
            list1.insertAt(i+1 ,nums);
        }
        return list1;
    }

    static void  funTest() {
        List list = new SeqList(10);
        for (int i = 1; i <= 10; i++) {
            list.insertAt(i,i);
        }
        System.out.print("插入之后顺序表的元素:");
        list.display();
        System.out.println("顺序表的长度"+list.getSize());
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入要删除的序号(从1开始):");
        int a = sc.nextInt();
        list.removeAt(a);
        System.out.print("删除第"+a+"个元素之后顺序表的元素:");
        list.display();
        System.out.println("顺序表的长度"+list.getSize());
        System.out.print("请输入两个值(第一个为准备在那个元素之后插入值，第二个为要插入的值)：");
        int b = sc.nextInt();
        int c = sc.nextInt();
        list.insertAt(b+1,c);
        System.out.print("插入之后顺序表的元素：");
        list.display();
        System.out.print("请输入要删除的值：");
        int d=sc.nextInt();
        list.remove(d);
        System.out.print("删除之后顺序表的元素：");
        list.display();
    }

    static void mergeTest(int size) {
        List list1 = new SeqList(size);
        List list2 = new SeqList(size);
//        merge空间使用完
        for (int i = 0; i < size; i++) {
            list1.insertAt(i+1,i*2);
            list2.insertAt(i+1,2*i+1);
        }
        List list3 = new SeqList(size);
        List list4 = new SeqList(size);
//        merge1空间未使用完
        for (int i = 0; i < size/2; i++) {
            list3.insertAt(i+1,i*2);
            list4.insertAt(i+1,2*i+1);
        }
//        list1.display();
//        list2.display();
        System.out.println(size+"个数据与"+size/2+"个数据比较效率");
        long startTime = System.currentTimeMillis();
        merge(list1,list2);                         // n（log n）
        long endTime = System.currentTimeMillis();
        System.out.println("merge程序运行时间：" + (endTime - startTime) + "ms");

        long startTime1 = System.currentTimeMillis();
        merge1(list3,list4);                        // n * n
        long endTime1 = System.currentTimeMillis();
        System.out.println("merge1程序运行时间：" + (endTime1 - startTime1) + "ms");
    }
}




